/*************************************************************************
 * File Name:    TwoSum.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/7 0:32:09
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Two Sum
 | Given an array of integers, find two numbers such that they add up to a specific target number.
 |
 | The function twoSum should return indices of the two numbers such that they add up to the target,
 | where index1 must be less than index2. Please note that your returned answers
 | (both index1 and index2) are not zero-based.
 |
 | You may assume that each input would have exactly one solution.
 |
 | Input: numbers={2, 7, 11, 15}, target=9
 | Output: index1=1, index2=2
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

bool cmp(const pair<int,int> &a, const pair<int,int> &b) { return a.first < b.first; }

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target)
    {
        vector<int> ans(2,0);
        
        vector<pair<int, int> > num;
        for (size_t i = 0; i < numbers.size(); ++i) {
            num.push_back(make_pair(numbers[i], i + 1));
        }
        sort(num.begin(), num.end(), cmp);
        
        int left = 0, right = num.size() - 1;
        while (left < right) {
            if (num[left].first + num[right].first == target) {
                ans[0] = num[left].second;
                ans[1] = num[right].second;
                if (ans[0] > ans[1]) swap(ans[0], ans[1]);
                break;
            } else if (num[left].first + num[right].first < target) {
                ++left;
            } else {
                --right;
            }
        }
        return ans;
    }
};

